package list;

public class LeetCode92 {

    public static void main(String[] args) {
        ListNode head = new ListNode(3, new ListNode(5));
        System.out.println(new LeetCode92().reverseBetween(head, 1, 2));
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head.next == null) return head;

        ListNode dummy = new ListNode(-501, head);

        int step = 0;
        ListNode leftNode = null;
        ListNode rightNode;

        ListNode pre = null;
        ListNode next = null;

        ListNode p = dummy;
        while (p != null) {
            if (step == left - 1) {
                pre = p;
            }
            if (step == left) {
                leftNode = p;
            }
            if (step == right) {
                rightNode = p;
                next = rightNode.next;
                rightNode.next = null;
            }
            p = p.next;
            step++;
        }

        pre.next = reverseList(leftNode);
        leftNode.next = next;
        return dummy.next;
    }

    public ListNode reverseList(ListNode head) {
        ListNode res = null;
        ListNode p = head;
        while (p != null) {
            ListNode next = p.next;
            p.next = res;
            res = p;
            p = next;
        }
        return res;
    }

}
